package medium;

/**
 *  假设dp[i,j]表示第i个到第j个最大水量,则dp[i,j]=max(dp[i,j-1],max(f[0~j,j]))
 *  最优解：双指针
 */
public class T11 {
    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(maxArea(height));
    }

    public static int maxArea(int[] height) {
        return dp(height, 0, height.length - 1, new int[height.length]);
    }

    // 计算i,j的最大水量
    public static int dp(int[] height, int i, int j, int[] max) {
        if (i == 0 && j == 1) {
            int area = Math.min(height[i], height[j]) * (j - i);
            max[j] = area;
            return area;
        } else {
            int max1;
            if (max[j - 1] == 0) {
                max1 = dp(height, i, j - 1, max);
                max[j] = max1;
            } else {
                max1 = max[j - 1];
            }
            int max2 = 0;
            for (int k = 0; k < j; k++) {
                int area;
                area = f(height, k, j);
                if (area > max2) {
                    max2 = area;
                }
                if (height[k]>=height[j]){
                    break;
                }
            }
            return Math.max(max1, max2);
        }
    }

    // 计算i,j的水量
    public static int f(int[] height, int i, int j) {
        return Math.min(height[i], height[j]) * (j - i);
    }

}
